package day_7_13;

public class Main2 {
    /**
     * 124. 二叉树中的最大路径和
     * https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    int ret = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ret;
    }

    public int dfs(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftVal = dfs(root.left);
        int rightVal = dfs(root.right);
        ret = Math.max(ret,(leftVal + rightVal + root.val));
        return Math.max(Math.max(leftVal,rightVal) + root.val,0);
    }
}
